#ifndef __REVERSELIST_H__
#define __REVERSELIST_H__
#include "ListHeader.h"

/*
* leetcode 206 翻转链表
*/

//双指针翻转链表
List* ReverseList(List* head) {
	//尾插法, 类似栈的添加元素的过程
	List* cur = head;
	List* next = nullptr;
	
	/*
	* 通过 cur 和 next, 来模拟栈的插入
	* 当 cur 为 nullptr 时, 代表链表已经遍历到末尾, 不需要进行插入
	*/
	while (cur != nullptr) {
		List* temp = cur->next;

		//整个过程相当于将链表的所有结点的 next 指针指向前一个结点
		//达到翻转链表的效果
		cur->next = next;
		next = cur;
		cur = temp;
	}

	return next;
}

//递归翻转链表
List* ReverseList(List* next, List* cur) {
	if (cur == nullptr)
		return next;

	List* temp = cur->next;
	cur->next = next;
	next = cur;

	return ReverseList(next, temp);
}

#endif // !__REVERSELIST_H__

